package geekstudy.week9;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 37. 解数独
 * https://leetcode-cn.com/problems/sudoku-solver/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了93.46% 的用户
 * 内存消耗：35.6 MB, 在所有 Java 提交中击败了92.28% 的用户
 */
public class Week9SudokuSolver {


    boolean[][] rowArray = new boolean[9][9];
    boolean[][] columnArray = new boolean[9][9];
    boolean[][][] subBlockArray = new boolean[3][3][9];
    List<int[]> spaceList = new ArrayList<int[]>();
    boolean valid = false;



    public void solveSudoku(char[][] board) {



        for(int row = 0; row < 9; row++) {
            for(int column = 0; column < 9; column++) {
                if(board[row][column] == '.') {
                    spaceList.add(new int[]{row, column});
                } else {
                    int digit = board[row][column] - '0' - 1;
                    rowArray[row][digit] = true;
                    columnArray[column][digit] = true;
                    subBlockArray[row / 3][column / 3][digit] = true;
                }
            }
        }
        // dfs(board, 0, rowArray, columnArray, subBlockArray, spaceList, valid);
        dfs(board, 0);
    }

    // boolean[][] rowArray, boolean[][] columnArray, boolean[][][] subBlockArray, List<int[]> spaceList, boolean valid
    public void dfs(char[][] board, int pos) {
        if(pos == spaceList.size()) {
            valid = true;
            return;
        }
        int[] space = spaceList.get(pos);
        int i = space[0];
        int j = space[1];
        for(int digit = 0; digit < 9 && !valid; digit++) {
            if(!rowArray[i][digit] && !columnArray[j][digit] && !subBlockArray[i / 3][j / 3][digit]) {
                rowArray[i][digit] = columnArray[j][digit] = subBlockArray[i / 3][j / 3][digit] = true;
                board[i][j] = (char)(digit + '0' + 1);
                // dfs(board, pos + 1, rowArray, columnArray, subBlockArray, spaceList, valid);
                dfs(board, pos + 1);
                rowArray[i][digit] = false;
                columnArray[j][digit] = false;
                subBlockArray[i / 3][j / 3][digit] = false;
            }
        }
    }


}
